GPU acceleration of Newton's method for large systems of polynomial equations in double double and quad double arithmetic

摘要

In order to compensate for the higher cost of double double and quad doublearithmetic when solving large polynomial systems, we investigate theapplication of NVIDIA Tesla K20C general purpose graphics processing unit. Thefocus on this paper is on Newton's method, which requires the evaluation of thepolynomials, their derivatives, and the solution of a linear system to computethe update to the current approximation for the solution. The reverse mode ofalgorithmic differentiation for a product of variables is rewritten in a binarytree fashion so all threads in a block can collaborate in the computation. Fordouble arithmetic, the evaluation and differentiation problem is memory bound,whereas for complex quad double arithmetic the problem is compute bound. Withacceleration we can double the dimension and get results that are twice asaccurate in about the same time.